﻿//#define _CRT_SECURE_NO_WARNINGS
//
////题目:
////给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
////
////输入格式:
////第一行包含两个整数 n 和 k。
////
////第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。
////
////输出格式:
////输出一个整数，表示数列的第 k 小数。
////
////数据范围:
////1≤n≤100000,
////1≤k≤n
////
////输入样例：
////5 3
////2 4 1 5 3
////
////输出样例：
////3
//
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 100010;
//int ans[N];
//int n, k;
//
//int sort_k(int l, int r) {
//    if (l == r) return ans[l];
//
//    int target = ans[(l + r) >> 1], L = l - 1, R = r + 1;
//    while (L < R) {
//        do {
//            L++;
//        } while (ans[L] < target);
//        do {
//            R--;
//        } while (ans[R] > target);
//
//        if (L < R && ans[L] > ans[R]) {
//            int temp = ans[L];
//            ans[L] = ans[R];
//            ans[R] = temp;
//        }
//    }
//
//    // 快速选择排序，就是在(快速排序的基础上)递归下去的时候判断一下，k 下标是在左边还是在右边
//    // 节约不必要的递归，达到效率的提高
//    if (R >= k)
//        return sort_k(l, R);
//    else
//        return sort_k(R + 1, r);
//}
//
//int main(void) {
//    cin >> n >> k;
//    // 看题目问的，第 k 个数，是从下标为 1 开始的哦
//    for (int i = 1; i <= n; i++) cin >> ans[i];
//    cout << sort_k(1, n) << endl;
//
//    return 0;
//}
//
